In this paper we propose an algorithm for recovering sparse orthogonalpolynomials using stochastic collocation. Our approach is motivated by thedesire to use generalized polynomial chaos expansions (PCE) to quantifyuncertainty in models subject to uncertain input parameters. The standardsampling approach for recovering sparse polynomials is to use Monte Carlo (MC)sampling of the density of orthogonality. However MC methods result in poorfunction recovery when the polynomial degree is high. Here we propose a generalalgorithm that can be applied to any admissible weight function on a boundeddomain and a wide class of exponential weight functions defined on unboundeddomains. Our proposed algorithm samples with respect to the weightedequilibrium measure of the parametric domain, and subsequently solves apreconditioned $\ell^1$-minimization problem, where the weights of the diagonalpreconditioning matrix are given by evaluations of the Christoffel function. Wepresent theoretical analysis to motivate the algorithm, and numerical resultsthat show our method is superior to standard Monte Carlo methods in manysituations of interest. Numerical examples are also provided that demonstratethat our proposed Christoffel Sparse Approximation algorithm leads tocomparable or improved accuracy even when compared with Legendre and Hermitespecific algorithms.
展开▼
